\chapter{数据结构}
\section{线性表}
线性表简称表,是零个或多个元素的有穷序列,通常可
以表示成$k_0 ,k_1 , \ldots,k_{n-1} (n \geq 1)$
\begin{itemize}
	\item 表目:线性表中的元素(可包含多个数据项,记录)
	\item 索引(下标):i 称为表目 k i 的“索引”或“下标”
	\item 表的长度:线性表中所含元素的个数 n
	\item 空表:长度为零的线性表 ( n = 0 )
\end{itemize}
\textbf{线性表特点:}操作灵活,其长度可以增长、缩短。\\
二元组$R,K={a_0,a_1,\ldots,a_{n-1},R = {r}}$
\begin{itemize}
	\item 有一个唯一的 开始结点 ,它没有前驱,有一个唯一的直接后继。
	\item  一个唯一的 终止结点 ,它有一个唯一的直接前驱,而没有后继。
	\item 其它的结点皆称为 内部结点 ,每一个内部结点都有且仅有一个唯一的直
	      接有前驱,也有一个唯一的直接后继。
	      $<a_i,a_{i+1}>a_i$ 是$a_{i+1}$ 的前驱,$a_{i+1}$是$a_i$ 的后继
	\item 前驱/后继关系r,具有 反对称性 和 传递性
\end{itemize}
\begin{figure}[!ht]
	\centering
	\includegraphics[width=\textwidth]{ds_1.png}
	\caption{链式结构}
\end{figure}
\textbf{线性结构的特点}
\begin{itemize}
	\item 均匀性:虽然不同线性表的数据元素可以是各种各样
	      的,但对于同一线性表的各数据元素必定具有相同的
	      数据类型和长度
	\item 有序性:各数据元素在线性表中都有自己的位置,且
	      数据元素之间的相对位置是线性的
\end{itemize}
\textbf{线性结构的分类}
\begin{itemize}
	\item 按复杂程度划分
	      \begin{itemize}
		      \item 简单的:线性表、栈、队列、散列表
		      \item 高级的:广义表、多维数组、文件......
	      \end{itemize}
	\item 按访问方式划分
	      \begin{itemize}
		      \item 直接访问型 (direct access)
		      \item 顺序访问型 (sequential access)
		      \item 目录索引型 (directory access)
	      \end{itemize}
	\item 按操作划分
	      \begin{itemize}
		      \item 线性表
		            \begin{itemize}
			            \item 所有表目都是同一类型结点的线性表
			            \item  不限制操作形式
			            \item 根据存储的不同分为:顺序表,链表
		            \end{itemize}
		      \item 栈（LIFO）插入和删除操作都限制在表的同一端进
		      \item 队列（FIFO）插入操作在表的一端, 删除操作在另一端
	      \end{itemize}
\end{itemize}
线性表的主要属性包括：
\begin{itemize}
	\item 主要属性包括
	\item 表头
	\item 线性表的长度
	\item 表头 (head)
	\item 表尾 (tail)
	\item 当前位置 (current position)
\end{itemize}
\textbf{顺序表}
\begin{itemize}
	\item 按索引值从小到大存放在一片相邻的连续区域
	\item 紧凑结构,存储密度为 1
\end{itemize}
\subsection{线性表实现方法的比较}
顺序表的主要优点
\begin{itemize}
	\item 没有使用指针,不用花费额外开销
	\item 线性表元素的读访问非常简洁便利
\end{itemize}
\textbf{链表的主要优点}
\begin{itemize}
	\item  无需事先了解线性表的长度
	\item  允许线性表的长度动态变化
	\item  能够适应经常插入删除内部元素的情况
\end{itemize}
\textbf{总结}
\begin{itemize}
	\item 顺序表是存储静态数据的不二选择
	\item 链表是存储动态变化数据的良方
\end{itemize}
\textbf{顺序表}
\begin{itemize}
	\item 插入、删除运算时间代价 O(n),查找则可常数时间完成
	\item 预先申请固定长度的连续空间
	\item 如果整个数组元素很满,则没有结构性存储开销
\end{itemize}
\textbf{链表}\\
\begin{itemize}
	\item 插入、删除运算时间代价 O(1),但找第i个元素运算时间代价 O(n)
	\item 存储利用指针,动态地按照需要为表中新的元素分配存储空间
	\item 每个元素都有结构性存储开销
\end{itemize}
\textbf{顺序表和链表存储密度}
n 表示线性表中当前元素的数目,
P 表示指针的存储单元大小(通常为 4 bytes)
E 表示数据元素的存储单元大小
D 表示可以在数组中存储的线性表元素的最大数目
\textbf{空间需求}
\begin{itemize}
	\item 顺序表的空间需求为 DE
	\item 链表的空间需求为 n(P + E)
\end{itemize}
n 的临界值,即 n > DE / (P+E)
\begin{itemize}
	\item n 越大,顺序表的空间效率就更高
	\item 如果P = E,则临界值为 n = D / 2
\end{itemize}
顺序表不适用的场合
\begin{itemize}
	\item  经常插入删除时,不宜使用顺序表
	\item  线性表的最大长度也是一个重要因素
\end{itemize}
\textbf{链表不适用的场合}
\begin{itemize}
	\item 当读操作比插入删除操作频率大时,不应选择链表
	\item 当指针的存储开销,和整个结点内容所占空间相比其比例较大时,应该慎重选择
\end{itemize}
\textbf{顺序表和链表的选择}\\
顺序表
\begin{itemize}
	\item 结点总数目大概可以估计
	\item 线性表中结点比较稳定(插入删除少)
	\item n > DE / (P + E)
\end{itemize}
\textbf{链表}\\
\begin{itemize}
	\item 结点数目无法预知
	\item 线性表中结点动态变化(插入删除多)
	\item n < DE / (P + E)>
\end{itemize}

\textbf{链表}
\begin{itemize}
	\item 单链
	\item 双链
	\item 循环链
\end{itemize}
\begin{figure}[!ht]
	\centering
	\includegraphics[width=\textwidth]{ds_2.png}
	\caption{链接种类}
\end{figure}
栈（LIFO）插入和删除在表的同一端进行
\begin{figure}[!ht]
	\centering
	\includegraphics[width=\textwidth]{ds_3.png}
	\caption{栈的结构}
\end{figure}
\textbf{队列}：插入在表的一端，删除在表的另一端。

\textbf{线性表的类模板}
\begin{cpp}
	template <class T> class List {
			void clear();// 置空线性表
			bool isEmpty(); // 线性表为空时,返回 true
			bool append(const T value);// 在表尾添加一个元素 value,表的长度增 1
			bool insert(const int p, const T value);// 在位置 p 上插入一个元素 value,表的长度增 1
			bool delete(const int p);// 删除位置 p 上的元素,表的长度减 1
			bool getPos(int& p, const T value);// 查找值为 value 的元素并返回其位置
			bool getValue(const int p, T& value);// 把位置 p 元素值返回到变量 value
			bool setValue(const int p, const T value);// 用 value 修改位置 p 的元素值
		};
\end{cpp}
为了方便调试代码中添加了用于显示输出相关的成员函数。
\cppfile{code/DS/ex2/main.cpp}
\subsection{顺序表}
\textbf{顺序表：}也称向量,采用定长的一维数组存储结构

\textbf{主要特性}
\begin{itemize}
	\item 元素的类型相同
	\item 元素顺序地存储在连续存储空间中,每一个元素有唯一
	      的索引值
	\item 使用常数作为向量长度
	\item 数组存储
	      \begin{itemize}
		      \item  读写其元素很方便 ,通过下标即可指定位置
		      \item  只要确定了首地址,线性表中任意数据元素都可以随机存取。
	      \end{itemize}
\end{itemize}
\begin{figure}[!htb]\label{fig:ds_13}
	\centering
	\includegraphics[width=\textwidth]{ds_13.png}
	\caption{线性表存储示意图}
\end{figure}
元素地址计算如$Loc(k_i)=Loc(k_0)+c\times i,c=sizeof(ELEM)$

\textbf{顺序表的类定义}
\cppfile{code/DS/ex4/main.cpp}
顺序表插入示意图如\ref{fig:ds_13}
\begin{figure}[!htb]\label{fig:ds_13}
	\centering
	\includegraphics[width=\textwidth]{ds_13.png}
	\caption{顺序表插入示意图}
\end{figure}
顺序表和插入代码：
\begin{cpp}
	// 设元素的类型为T, aList是存储顺序表的数组, maxSize是其最大长度;
	// p为新元素value的插入位置,插入成功则返回true, 否则返回false
	template <class T> bool arrList<T> :: insert (const int p, const T value) {
			int i;
			if (curLen >= maxSize) { // 检查顺序表是否溢出
					cout << "The list is overflow"<< endl; return false;
				}
			if (p < 0 || p > curLen) { // 检查插入位置是否合法
					cout << "Insertion point is illegal"<< endl; return false;
				}
			for (i = curLen; i > p; i--)
			aList[i] = aList[i-1];
			// 从表尾 curLen -1 起往右移动直到 p
			aList[p] = value;
			// 位置 p 处插入新元素
			curLen++;
			// 表的实际长度增 1
			return true;

		}
\end{cpp}
\begin{figure}[!h]\label{fig:ds_15}
	\centering
	\includegraphics[width=\textwidth]{ds_15.png}
	\caption{删除示意图}
\end{figure}
\textbf{顺序表删除示意图}
\begin{cpp}
	// 设元素的类型为 T;aList是存储顺序表的数组; p 为即将删除元素的位置
	// 删除成功则返回 true,否则返回 false
	template <class T>
	// 顺序表的元素类型为 T
	bool arrList<T> :: delete(const int p) {
			int i;
			if (curLen <= 0 ) {
					// 检查顺序表是否为空
					cout << " No element to delete \n"<< endl;
					return false ;

				}
			if (p < 0 || p > curLen-1) { // 检查删除位置是否合法
					cout << "deletion is illegal\n"<< endl;
					return false ;
				}
			for (i = p; i < curLen-1; i++)
			aList[i] = aList[i+1];
			// 从位置p开始每个元素左移直到 curLen
			curLen--;
			// 表的实际长度减1
			return true;

		}
\end{cpp}
顺序表插入时间代价$M_i=\frac{n}{2}$,删除时间代价$M_d=\frac{n-1}{2}$
\subsection{链表}
通过指针把它的一串存储结点链接成一个链,存储结点由两部分组成:
\begin{itemize}
	\item  数据域
	\item 指针域(后继地址)
\end{itemize}
\begin{figure}[!ht]
	\centering
	\includegraphics[width=\textwidth]{ds_4.png}
	\caption{链表}
\end{figure}
\textbf{带头节点的单链表}

\begin{itemize}
	\item 整个单链表：head
	\item 第一个节点：head->next,head$\neq$NULL
	\item 空表判断：head->next == NULL,当前节点$a_1$:fence->next(curr隐含)
\end{itemize}
\begin{figure}[!h]
	\centering
	\includegraphics[width=\textwidth]{ds_5.png}
	\caption{单链表}
\end{figure}
单链表的节点类型：
\cppfile[firstline=7,lastline=18]{code/datastruct/tree/src/LinkNode.cpp}
单链表的类定义：

\cppfile[firstline=20,lastline=45]{code/DS/ex12/test3.cc}
查找单链表中第i个节点

\cppfile[firstline=46,lastline=62]{code/DS/ex12/test3.cc}
\textbf{单链表的插入}
\begin{figure}[!ht]
	\centering
	\includegraphics[width=\textwidth]{ds_5.png}
	\caption{单链表的插入示意图}
\end{figure}
\begin{enumerate}
	\item 创建新节点
	\item 新节点指向右边的节点
	\item 左边节点指向新节点
\end{enumerate}

\cppfile[firstline=84,lastline=103]{code/DS/ex12/test3.cc}
\textbf{单链表的删除}

从链表中删除节点
\begin{enumerate}
	\item 用p指向元素x的节点的前驱结点
	\item 释放元素x的结点
	\item 释放x占据的空间
\end{enumerate}
\begin{figure}[!ht]
	\centering
	\includegraphics[width=\textwidth]{ds_7.png}
	\caption{链表删除节点示意图}
\end{figure}
\begin{cpp}
	// 删除节点
	q = p->next;
	p->next = q->next;
	free(q);
\end{cpp}
删除节点的算法：
\cppfile[firstline=132,lastline=147]{code/DS/ex12/test3.cc}
对一个结点操作,必先找到它,即用一个指针指向它。
完整代码如下：
\cppfile{code/DS/ex12/test3.cc}
\begin{itemize}
	\item 找单链表中任一结点,都必须从第一个点开始
	      \begin{Textcode}
		      p = head;
		      while (没有到达) p = p->next;
	      \end{Textcode}
	\item 单链表的时间复杂度
	      \begin{itemize}
		      \item 定位:O(n)
		      \item 插入：O(x)+O(1)
		      \item 删除：O(n)+O(1)
	      \end{itemize}
\end{itemize}
单链表的next字段仅仅指向后继节点，不能有效的查找前去，反之亦然。添加指向前驱的指针
\begin{figure}[!ht]
	\centering
	\includegraphics[width=0.5\textwidth]{ds_8.png}
	\caption{双链节点示意图}
\end{figure}
\begin{figure}[!ht]
	\centering
	\includegraphics[width=\textwidth]{ds_9.png}
	\caption{双链示意图}
\end{figure}
双链节点和结构定义：
\begin{cpp}
	template <class T> class Link {
			public:
			T data;
			// 用于保存结点元素的内容
			Link<T> * next;
			// 指向后继结点的指针
			Link<T> *prev;
			// 指向前驱结点的指针
			Link(const T info, Link<T>* preValue = NULL, Link<T>* nextValue = NULL) {
					// 给定值和前后指针的构造函数
					data = info;
					next = nextValue;
					prev = preValue;

				}
			Link(Link<T>* preValue = NULL, Link<T>* nextValue = NULL) {
					// 给定前后指针的构造函数
					next = nextValue;
					prev = preValue;

				}

		}
\end{cpp}
\begin{figure}[!ht]
	\centering
	\includegraphics[width=\textwidth]{ds_10.png}
	\caption{双链插入节点示意图}
\end{figure}
\ref{fig:ds_11}是删除节点的示意图
\begin{figure}[!ht]\label{dif:ds_11}
	\centering
	\includegraphics[width=\textwidth]{ds_11.png}
	\caption{双链删除节点}
\end{figure}

\begin{cpp}
	p->prev->next=p->next
	p->next->prev=p->prev
	p->next=NULL
	p->prev=NULL
\end{cpp}
\textbf{循环链}

将单链表或者双链表的头尾结点链接起来,就是一个循，环链表，不增加额外存储花销,却给不少操作带来了方便， 从循环表中任一结点出发,都能访问到表中其他结点。循环链示意图如\ref{fig:ds_12}
\begin{figure}[!ht]\label{fig:ds_12}
	\centering
	\includegraphics[width=\textwidth]{ds_12.png}
	\caption{循环链示意图}
\end{figure}
\textbf{链表的边界条件}

\begin{itemize}
	\item 几个特殊点的处理
	      \begin{itemize}
		      \item  头指针处理
		      \item  非循环链表尾结点的指针域保持为 NULL
		      \item  循环链表尾结点的指针回指头结点
	      \end{itemize}
	\item 链表处理
	      \begin{itemize}
		      \item 空链表的特殊处理
		      \item 插入或删除结点时指针勾链的顺序
		      \item 指针移动的正确性
		      \item 插入
		      \item 查找或遍历
	      \end{itemize}

\end{itemize}
\textbf{队列的应用：}
农夫过河，现在有农夫，羊，狼，人，菜。农夫每次能带一个物品过河，羊和狼，羊和菜不能在人不在的时候在同一边，输出过河方式。
\cppfile{code/STL/arith/main.cpp}




































\section{创建基本的数据结构}
线性表相关
\subsection{顺序表}
顺序表要实现的功能有:
\begin{itemize}
	\item 清空顺序表(\cppinline{void clear()})
	\item 判断顺序表是否为空(\cppinline{void isEmpty()})
	\item 在顺序表尾部添加元素\cppinline{(bool append(const T value))}
	\item 在位置p删除元素\cppinline{(bool insert(const int p,const T value))}
	\item 获取值为value的索引(\cppinline{bool delete(const int p))}
	\item 获取位置p的元素\cppinline{value(bool getPos(int& p,const T value))}
	\item 设置位置p的元素\cppinline{(bool setValue(const int p,const T value));}
\end{itemize}

\subsection{单链表}
单链表数据结构包括数据域和指针域。数据域用来存储数据元素的值，指针域用来指向下一个节点。
\begin{cpp}
	typedef struct Node{
			int value;
			Node * next;
		}
\end{cpp}
单链表应该包含的功能:
\begin{itemize}
	\item 删除单链表中的一个元素
	\item 获取单链表中的一个元素
	\item 修改单链表中的一个元素
	\item 清除单链表
	\item 获取单链表的长度
\end{itemize}

